/*
*from http://en.wikipedia.org/wiki/Mergesort
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main(void)
{
  std::vector<unsigned> data;

  for(unsigned i = 0; i < 10; i++)
    data.push_back(i);

  std::random_shuffle(data.begin(), data.end());

  std::cout << "Initial: ";

  std::copy(data.begin(),data.end(),std::ostream_iterator<unsigned>(std::cout," "));
  std::cout << std::endl;

  for(unsigned m = 1; m <= data.size(); m *= 2)
  {
    for(unsigned i = 0; i < data.size() - m; i += m * 2)
    {
      std::inplace_merge(
        data.begin() + i,
        data.begin() + i + m,
        data.begin() + std::min<unsigned>(i + m * 2, (unsigned)data.size()));
    }
  }

  std::cout << "Sorted:  ";

  std::copy(data.begin(),data.end(),std::ostream_iterator<unsigned>(std::cout," "));
  std::cout << std::endl;

  return 0;
}
